/*
 * https://leetcode-cn.com/problems/open-the-lock/
 * bfs开密码锁
 */
typedef struct {
    char ch[5];
    int cnt;
    UT_hash_handle hh;
} ut_hash_t;

ut_hash_t *visited_map = NULL;
ut_hash_t *dead_map = NULL;
void plus_minus_one(char *cur, int j, char *next, int one)
{
    strcpy(next, cur);
    next[j] = cur[j] + one;
    if (next[j] > '9') {
        next[j] = '0';
        return;
    }
    if (next[j] < '0') next[j] = '9';
}
int openLock(char ** deadends, int deadendsSize, char * target){
    dead_map = NULL;
    visited_map = NULL;
    ut_hash_t *s = NULL;
    for (int i = 0; i < deadendsSize; i++) {
        s = (ut_hash_t*)malloc(sizeof(ut_hash_t));
        strcpy(s->ch, deadends[i]);
        HASH_ADD_STR(dead_map, ch, s);
    }
    char que[10000][5] = {0};
    int res = 0;
    int start = 0;
    int end = 1;
    int cnt = 1;
    strcpy(que[0], "0000");
    s = (ut_hash_t*)malloc(sizeof(ut_hash_t));
    strcpy(s->ch, "0000");
    HASH_ADD_STR(visited_map, ch, s);
    while (start < cnt) {
        for (int k = start; k < end; k++) {
            ut_hash_t *tmp = NULL;
            HASH_FIND_STR(dead_map, que[k], tmp);
            if (tmp != NULL) continue; // 存在于 deadend中
            if (strcmp(que[k], target) == 0) return res;
            for (int j = 0; j < 4; j++) {
                char pls[5] = "0000";
                plus_minus_one(que[k], j, &pls, 1);
                tmp = NULL;
                HASH_FIND_STR(visited_map, pls, tmp); // 检查是否已访问
                if (tmp == NULL) {
                    tmp = (ut_hash_t*)malloc(sizeof(ut_hash_t));
                    strcpy(tmp->ch, pls);
                    HASH_ADD_STR(visited_map, ch, tmp);
                    strcpy(que[cnt++], pls); // 加入队列末端
                }
                char mins[5] = "0000";
                plus_minus_one(que[k], j, mins, -1);
                tmp = NULL;
                HASH_FIND_STR(visited_map, mins, tmp);
                if (tmp == NULL) {
                    tmp = (ut_hash_t*)malloc(sizeof(ut_hash_t));
                    strcpy(tmp->ch, mins);
                    HASH_ADD_STR(visited_map, ch, tmp);
                    strcpy(que[cnt++], mins); // 加入队列末端
                }
            }
        }
        res++;
        start = end;
        end = cnt;
    }
    
    return -1;
}